-- Queens.hs
-- Copyright (C) 2013 Liu Xinyu (liuxinyu95@gmail.com)
-- 
-- This program is free software: you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation, either version 3 of the License, or
-- (at your option) any later version.
-- 
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
-- 
-- You should have received a copy of the GNU General Public License
-- along with this program.  If not, see <http://www.gnu.org/licenses/>.

module Queens where

import Data.List ((\\))

-- DFS find 92 distinct solutions
solve = dfsSolve [[]] [] where
    dfsSolve [] s = s
    dfsSolve (c:cs) s
             | length c == 8 = dfsSolve cs (c:s)
             | otherwise = dfsSolve ([(x:c) | x <- [1..8] \\ c, not $ attack x c] ++ cs) s
    attack x cs = let y = 1 + length cs in 
                 any (\(c, r) -> abs(x - c) == abs(y - r)) $ zip (reverse cs) [1..]


-- TODO: constructive find 12 unique solutions (not remove duplicates, but avoid duplicate)
-- One idea is to limit the queue in the 1st row within half, which generate 46 solutions,
-- While there are still solutions can be generated by rotating in other angles (and flip)
